package leetcode.algorithm.dynamicPlan;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;


/**
 * 200. 岛屿数量
 */

class SolutionModel015 {

    public static void main(String[] args) {
        SolutionModel015 s = new SolutionModel015();
        char[][] grid = {{'1','1','1'},{'0','1','0'},{'1','1','1'}};

        s.numIslands(grid);
    }

    int num = 0;
    public int numIslands(char[][] grid) {
        boolean[][] isUsed = new boolean[grid.length][grid[0].length];
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[0].length; j++){
                if(grid[i][j]=='1'){
                    boolean temp = isUsed[i][j];
                    dfs(isUsed, grid, i, j);
                    if(temp!=isUsed[i][j])num++;
                }
            }
        }
        return num;
    }


    public void dfs(boolean[][] isUsed, char[][] grid, int x, int y){
        if(isUsed[x][y]){
            return;
        }
        isUsed[x][y] = true;
        if(y+1<grid[0].length && grid[x][y+1]=='1')dfs(isUsed, grid, x, y+1);
        if(x+1<grid.length && grid[x+1][y]=='1')dfs(isUsed, grid, x+1, y);
        if(y-1>=0 && grid[x][y-1]=='1')dfs(isUsed, grid, x, y-1);
        if(x-1>=0 && grid[x-1][y]=='1')dfs(isUsed, grid, x-1, y);

    }

}

public class NewSept {
    //    static
    public static void main(String[] args) {
        int a = 1;
        String o = "s";
        System.out.println(o.substring(0,0));
        char[] arr = new char[2];

        List ls = new ArrayList();
        ls.add("s");
        fix(a,o, ls, arr);
        System.out.println(a + " : " + o + " : " + ls+ " : " + arr[0]);
    }

    private static void fix(int a, String o, List ls, char[] arr) {
        a = 2;
        o = "os";
        ls.add(1);
        arr[1] = '1';
    }
}

/**
 * 6230. 长度为 K 子数组中的最大和(连续)
 */
class SolutionModel013 {
    public static void main(String[] args) {
        SolutionModel013 s = new SolutionModel013();
//        int[] nums = {1,5,4,2,9,9,9};
        //[1,1,1,7,8,9][9,18,10,13,17,9,19,2,1,18]
        //5
        //3
        int[] nums = {9,18,10,13,17,9,19,2,1,18};
        int k = 5;
        s.maximumSubarraySum(nums, k);
    }

    int max;
    int curNum=0;
    public long maximumSubarraySum(int[] nums, int k) {
        Deque<Integer> ls = new LinkedList<>();

        recursion(ls, nums, k);
        return max;
    }

    public void recursion( Deque<Integer> ls, int[] nums, int k){

        for(int i=0; i<nums.length-k+1; i++) {
            System.out.println(i);
            if (ls.isEmpty()) {
                while (i < nums.length) {
                    if (ls.contains(nums[i])) {
                        ls.clear();
                    }
                    ls.add(nums[i]);
                    i++;
                    if (ls.size() == k) {
                        curNum = 0;
                        for (Integer s : ls) curNum += s;
                        max = Math.max(curNum, max);
                        i = i - k;
                        break;
                    }
                }
            } else {
                int num = ls.removeFirst();
                if (ls.contains(nums[i + k - 1])) {
                    curNum -= num;
                    ls.add(nums[i + k - 1]);
                } else {
                    curNum -= num;
                    ls.add(nums[i + k - 1]);
                    curNum += nums[i + k - 1];
                    max = Math.max(curNum, max);

                }
            }
            System.out.println(ls + " = sum : " + max);
        }


    }
}

/**
 * 6230. 长度为 K 子数组中的最大和（非连续）
 */
class SolutionModel014 {
    public static void main(String[] args) {
        SolutionModel013 s = new SolutionModel013();
        int[] nums = {1,5,4,2,9,9,9};
        int k = 3;
        s.maximumSubarraySum(nums, k);
    }
    int max;
    int temp;
    public long maximumSubarraySum(int[] nums, int k) {

        boolean[] isUsed = new boolean[nums.length];
        List<Integer> ls = new ArrayList<>();

        recursion(ls, isUsed, nums, k);
        return max;
    }

    public void recursion( List<Integer> ls, boolean[] isUsed, int[] nums, int k){
        if(ls.size()>=3){
            temp = 0;
            ls.stream().forEach(s->{temp += s;});
            max = Math.max(temp, max);
            System.out.println(ls + " = sum : " + max);
            return;
        }

        for(int i=0; i<nums.length; i++){
            if(!isUsed[i]&&!ls.contains(nums[i])){
                isUsed[i] = true;
                ls.add(nums[i]);
                recursion(ls, isUsed, nums, k);
                isUsed[i] = false;
                ls.remove(ls.size()-1);
            }
        }
    }
}

class SolutionModel012 {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>() ;
        set.add(1);
        set.add(1);
//        set.size()

    }
}

/**
 * 215. 207. 课程表
 */
class SolutionModel011 {
    public static void main(String[] args) {
        SolutionModel011 s = new SolutionModel011();
        int numCourses = 2;
//        int[][] prerequisites = {{1,0},{2,6},{1,7},{6,4},{7,0},{0,5}};

        int[][] prerequisites = {{0,1},{2,3},{1,2},{3,0}};
            List<List<Integer>> list = new ArrayList<>();
            List<Integer> ls = new ArrayList<>();
            for (int i = 0; i < prerequisites.length; i++) {
                for (int j = 0; j < prerequisites[0].length; j++) {
                    ls.add(prerequisites[i][j]);
                }
                list.add(new ArrayList<>(ls));
                ls.clear();
            }

            list = list.stream().sorted(Comparator.comparing(o -> o.get(0))).collect(Collectors.toList());
            for (int i = 0; i < list.size(); i++) {
                for (int j = 0; j < list.get(0).size(); j++) {
                    prerequisites[i][j] = list.get(i).get(j);
                }
            }
//        String s1 = Arrays.toString(prerequisites);
//        System.out.println(s1);

        //4
        //[[0,1],[2,3],[1,2],[3,0]]
        int[] nums = {3,3,1,3,1};
        boolean b = s.canFinish(numCourses, prerequisites);
        System.out.println(b);

    }


    public boolean canFinish(int numCourses, int[][] prerequisites) {
        boolean flag = true;
        for(int i=0;i<prerequisites.length;i++){
            Set<Integer> set = new HashSet<>();
            set.add(prerequisites[i][0]);
            if(!recursion(prerequisites, set, i, flag,0)){
                return false;
            }
//            set.clear();
        }

        return true;
    }


    public boolean recursion(int[][] prerequisites, Set<Integer> set, int curPoint,  boolean flag, int useNum){
        if(!flag){
            return false;
        }

        for(int j=useNum;j<prerequisites.length;j++){
            if( curPoint!=j&&prerequisites[curPoint][1]==prerequisites[j][0]){
                curPoint = j;
                if(!set.add(prerequisites[j][1])){
                    System.out.println("Flase : Th " + j + " : " + set);
                    return false;
                }
                System.out.println("Th " + j + " : " + set);
                Set<Integer> temp = new HashSet<>(set);
                flag = recursion(prerequisites, set, curPoint, flag, j);
                set = temp;
            }
        }
        return flag;

    }
}
/**
 * 215. 数组中的第K个最大元素    快速排序
 */
class SolutionModel010 {
    public static void main(String[] args) {
        SolutionModel010 s = new SolutionModel010();
        int[] nums = {3,3,1,3,1};
        s.quickSort(nums, 0, nums.length-1);
    }

    public void quickSort(int[] nums, int l, int r){
        int i,j, mid, temp;

        if(l>r){
            return;
        }
        i = l;
        j = r;
        mid = l;

        while(l<r){
            while(nums[r]>=nums[mid]&&r>l){
                r--;
            }
            while(nums[l]<=nums[mid]&&l<r){
                l++;
            }

            if(l<r){
                temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
            }
        }
        System.out.println(r + " " + l);

        temp = nums[mid];
        nums[mid] = nums[l];
        nums[l] = temp;
        String string = Arrays.toString(nums);
        System.out.println(string);

        quickSort(nums,i,l-1);
        quickSort(nums, r+1, j);

    }
}

class QuickSort {
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];

        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }


    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        String string = Arrays.toString(arr);
        System.out.println(string);

    }
}
/**
 * 142. 环形链表 II
 */
class SolutionModel009 {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();
        set.add(1);
        set.add(1);
        if(set.add(1)){

        }


    }
}


class ListN {
    public static void main(String[] args) {
        int[] nums = {1,23,1,4,5,12};
        List<Integer> ls = new ArrayList<>();
        for (int num : nums) {
            ls.add(num);
        }
        int mean = 3;
        Map<Integer, Long> collect = ls.stream().collect(Collectors.groupingBy(a -> {
            return a;
        }, Collectors.counting()));
        int res = 0;
        for (int s : collect.keySet()) {
            if(collect.get(s)>mean){
                res = s;
            }
        }


        System.out.println(collect);

        ListN l1 = new ListN(1);
        ListN l2 = new ListN(2);
        System.out.println(l1.equals(l1));
    }
    int val;
     ListNode next;
    ListN(int x) {
         val = x;
         next = null;
    }
 }

/**
 * 448. 找到所有数组中消失的数字
 */
class SolutionModel008 {

    public static void main(String[] args) {
        SolutionModel008 a01 = new SolutionModel008();
        int[] nums = {4,3,2,7,8,2,3,1,1};
        a01.findDisappearedNumbers(nums);
    }


    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ls = new ArrayList<>();
        for (int i : nums) {
            ls.add(i);
        }

        List<Integer> collect = ls.stream().distinct().sorted().collect(Collectors.toList());
        System.out.println(collect);
        ls.clear();
        int curNum = 0;
        for(int i=1; i<nums.length + 1 ;i++){
            if(collect.size()>curNum) {
                if (collect.get(curNum) == i) {
                    curNum++;
                } else {
                    ls.add(i);
                }
            }else{
                ls.add(i);
            }
        }
        System.out.println(ls);

        return ls;
    }
}

/**
 * 1620. 网络信号最好的坐标
 */
class SolutionModel007 {
    public static void main(String[] args) {
        SolutionModel007 a01 = new SolutionModel007();
        a01.letterCombinations("23");
    }
    Map<String, String> map = new HashMap<>();

    {
        map.put("2", "abc");
        map.put("3", "def");
        map.put("4", "ghi");
        map.put("5", "jkl");
        map.put("6", "mno");
        map.put("7", "pqrs");
        map.put("8", "tuv");
        map.put("9", "wxyz");
    }

    public List<String> letterCombinations(String digits) {


        List<String[]> list = new ArrayList<>();
        String[] temp = new String[digits.length()];
        for(int i=0;i<digits.length();i++){
            temp[i] = "!";
        }
        recursion(list, temp, digits, 0);

        List<String> stringList = list.stream().map(s -> {
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < s.length; i++) {
                str.append(s[i]);
            }
            return str.toString();
        }).collect(Collectors.toList());
        //
        List<Integer> list1 = new ArrayList<>();
        int[] nums = {1,23,4};
        for(int i:nums){
            list1 = list1.stream().filter(s->s!=i).collect(Collectors.toList());
        }
        System.out.println(stringList);

        return null;

    }

    public void recursion(List<String[]> list, String[] temp,String digits, int curNum){
        boolean isEmpty = true;
        for(int i=0;i<digits.length();i++){
            if(temp[i].equals("!")){
                isEmpty = false;
                break;
            }
        }
        if(isEmpty){
            String[] cur = new String[temp.length];
            for (int i = 0; i < cur.length; i++) {
                cur[i] = temp[i];
            }
            list.add(cur);
            return;
        }

        String curString = map.get(digits.substring(curNum, curNum+1));
        for(int i=0;i<curString.length();i++){
            temp[curNum] = curString.substring(i,i+1);
            recursion(list, temp, digits, curNum+1);
            temp[curNum] = "!";
        }

    }
}

/**
 * 1620. 网络信号最好的坐标
 */

class SolutionModel006 {
    public static void main(String[] args) {
        SolutionModel006 a01 = new SolutionModel006();
        int[][] towers = {{0,1,2},{2,1,2},{1,0,2},{1,2,2}};
        int radius = 1;
        a01.bestCoordinate(towers, radius);
    }

    public int[] bestCoordinate(int[][] towers, int radius) {
        int[] result = new int[2];
        if(towers.length<=1){
            if(towers[0][2]==0){
                result[0] = 0;
                result[1] = 0;
                return result;
            }
            result[0] = towers[0][0];
            result[1] = towers[0][1];
            return result;
        }
        int sign = 0, Maxsign=0;
        double distance =0.0;
        int MaxX = 0, MaxY = 0;
        for(int[] cur:towers){
            MaxX = Math.max(cur[0], MaxX);
            MaxY = Math.max(cur[1], MaxY);
        }
        //计算每一个点上的强度
        for(int x=0;x<=MaxX;x++){
            for(int y=0;y<=MaxY;y++){
                sign = 0;
                distance = 0;
                for(int j=0;j<towers.length;j++){
                    //计算距离
                    distance =  Math.sqrt(Math.pow((x-towers[j][0]),2)
                            +Math.pow((y-towers[j][1]),2));
                    System.out.println("distance " + distance);
                    if(distance<=radius){
                        //叠加信号值
                        sign += (int)Math.floor(towers[j][2]/(1+distance));
                    }

                }
                if(Maxsign<sign){
                    Maxsign = sign;
                    result[0] = x;
                    result[1] = y;
                }
                System.out.println("MaxY:" + x + " , " + y + ":" + "sign: " + sign);
            }
        }

        return result;
    }
}

/**
 * 1662. 检查两个字符串数组是否相等
 */

class SolutionModel005 {
    public static void main(String[] args) {
        String[] word1 = {"ab", "c"}, word2 = {"a", "bc"};
        StringBuilder s1 = new StringBuilder();
        StringBuilder s2 = new StringBuilder();
        Arrays.stream(word1).forEach(s->{
            s1.append(s);
        });
        Arrays.stream(word2).forEach(s->{
            s2.append(s);
        });

        System.out.println(s1.toString());
        System.out.println(s2.toString());
    }


}
/**
 * 生成所有的合理括号
 */
class SolutionModel004 {
    List<String> res = new ArrayList<>();

    public static void main(String[] args) {
        SolutionModel004 a003 = new SolutionModel004();
        a003.generateParenthesis(5);
    }

    public List<String> generateParenthesis(int n) {
        if(n <= 0){
            return res;
        }
        getParenthesis("",n,n);
        System.out.println(res);
        return res;
    }

    private void getParenthesis(String str,int left, int right) {
        if(left == 0 && right == 0 ){
            res.add(str);
            return;
        }
        if(left == right){
            //剩余左右括号数相等，下一个只能用左括号
            getParenthesis(str+"(",left-1,right);
        }else if(left < right){
            //剩余左括号小于右括号，下一个可以用左括号也可以用右括号
            if(left > 0){
                getParenthesis(str+"(",left-1,right);
            }
            getParenthesis(str+")",left,right-1);
        }
    }



}

/**
 * 生成所有的合理括号
 */
class SolutionModel003 {
    public static void main(String[] args) {
        SolutionModel003 a003 = new SolutionModel003();
        a003.generateParenthesis(5);
    }

    public List<String> generateParenthesis(int n) {
        n = n*2;

        List<List<String>> ls = new ArrayList<>();
        String[] cur = new String[n];
        for(int i=0; i<n; i++){
            if(i<n/2){
                cur[i] = "(";
            }else{
                cur[i] = ")";
            }
        }
        boolean[] isUsed = new boolean[n];
        List<String> list = new ArrayList<>() ;
        recursion(ls, n, list, cur, isUsed);
        List<String> collect = doValid(ls).stream().distinct().map(s -> {
            StringBuilder str = new StringBuilder();
            for (int i = 0; i < s.size(); i++) {
                str.append(s.get(i));
            }
            return str.toString();
        }).collect(Collectors.toList());
        System.out.println(collect);
        return null;
    }

    private List<List<String>> doValid(List<List<String>> ls) {

        return ls.stream().filter(s -> {
            int right = 0;
            int left = 0;
            for (int i = 0; i < s.size(); i++) {
                if (s.get(i) == "(") {
                    right++;
                } else {
                    left++;
                }
                if (left > right) {
                    return false;
                }
            }
            return true;
        }).collect(Collectors.toList());

    }

    public void recursion(List<List<String>> ls, int n, List<String> list, String[] cur, boolean[] isUsed){
        if(list.size()>=n){
            ls.add(new ArrayList<>(list));
            return ;
        }
        for(int i=0; i<n; i++){
            if(!isUsed[i]){
                isUsed[i]=true;
                list.add(cur[i]);
                recursion(ls, n, list, cur, isUsed);
                list.remove(list.size()-1);
                isUsed[i]=false;
            }
        }
    }

}


/**
 *
 */
class SolutionModel002 {

    //贪心
    public static void main(String[] args) {
        Long n = 615024862295L; int target = 7;
        makeIntegerBeautiful(n,target);
    }

    public static long makeIntegerBeautiful(long n, int target) {
        String s = String.valueOf(n);
        List<Long> list = new ArrayList<>();
        Long result = 0L;
        for (int i = s.length()-1; i >= 0 ; i--) {
            Long value = (long) Math.pow(10, s.length()-i-1);

            if(s.substring(i,i+1).equals("0")){

            }else{
                result += ((10-Long.valueOf(s.substring(i,i+1)))*value);
                s = String.valueOf(Long.valueOf(s)+(10-Long.valueOf(s.substring(i,i+1)))*value);
                if(judge(s)<target){
                    break;
                }
            }
            System.out.println(i+ ": " +s + "  result:" + result);
        }
        System.out.println(result);
        return result;
    }

    private static int judge(String s) {
        int num = 0;
        for (int i = 0; i < s.length(); i++) {
            num += Integer.valueOf(s.substring(i,i+1));
        }
        return num;
    }

}

/**
 *
 */
class SolutionModel001 {

    public static void main(String[] args) {
        String[] creators = {"alice","bob","alice","chris"}, ids = {"one","two","three","four"};
        int[] views = {5,10,5,4};
        List<List<String>> ls = mostPopularCreator(creators, ids, views);


    }
    public static List<List<String>> mostPopularCreator(String[] creators, String[] ids,
                                                            int[] views) {

        Map<String, Long> map = Arrays.stream(creators).collect(Collectors.groupingBy(String::toString, Collectors.counting()));
        List<String> list = map.keySet().stream().filter(s -> map.get(s) > 1).collect(Collectors.toList());
        List<String> list1 = map.keySet().stream().filter(s -> map.get(s) == 1).collect(Collectors.toList());
        Map<String, Integer> reMap = new HashMap<>();
        Map<String, String> reMap1 = new HashMap<>();
        list.stream().forEach(s->{
            int total = 0;
            boolean flag = false;
            int preRecord = 0;
            for(int i=0;i<creators.length;i++){
                if(s.equals(creators[i])){
                    if(views[i]>preRecord||flag==false){
                        reMap1.put(s,ids[i]);
                        preRecord = views[i];
                        flag=true;
                    }
                    total+=views[i];
                }
            }
            reMap.put(s,total);

        });
        list1.stream().forEach(s->{
            for(int i=0;i<creators.length;i++){
                if(s.equals(creators[i])){
                    reMap1.put(s,ids[i]);
                    reMap.put(s,views[i]);;
                }
            }
        });
        List<Integer> collect = reMap.values().stream().sorted().collect(Collectors.toList());
        System.out.println(collect);
        Integer maxValue = collect.get(0);
        System.out.println(reMap);
        System.out.println(reMap1);
        List<String> collect1 = reMap.keySet().stream().filter(s ->
                reMap.get(s) == maxValue
        ).collect(Collectors.toList());
        Map<String, String> result = new HashMap<>();
        collect1.stream().forEach(s->{
            if(reMap1.keySet().contains(s)){
                result.put(s, reMap1.get(s));
            }
        });
        List<List<String>> reslist = new ArrayList<>();
        result.keySet().stream().forEach(s->{
            List<String> temp = new ArrayList<>();
            temp.add(s);
            temp.add(result.get(s));
            reslist.add(temp);
        });

        System.out.println(reslist);
        return  null;

    }
}

class DemoCase{

    public static void main(String[] args) {
        String[] creators = {"alice","alice","alice", "123"};
        List<String> collect = Arrays.stream(creators).filter(s -> s.equals("123")).collect(Collectors.toList());
        System.out.println(collect);
    }
}